/*
 * @lc app=leetcode.cn id=934 lang=cpp
 *
 * [934] 最短的桥
 *
 * https://leetcode.cn/problems/shortest-bridge/description/
 *
 * algorithms
 * Medium (47.89%)
 * Likes:    254
 * Dislikes: 0
 * Total Accepted:    34K
 * Total Submissions: 71.1K
 * Testcase Example:  '[[0,1],[1,0]]'
 *
 * 在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）
 *
 * 现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。
 *
 * 返回必须翻转的 0 的最小数目。（可以保证答案至少是 1 。）
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：A = [[0,1],[1,0]]
 * 输出：1
 *
 *
 * 示例 2：
 *
 *
 * 输入：A = [[0,1,0],[0,0,0],[0,0,1]]
 * 输出：2
 *
 *
 * 示例 3：
 *
 *
 * 输入：A = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
 * 输出：1
 *
 *
 *
 * 提示：
 *
 *
 * 2
 * A[i][j] == 0 或 A[i][j] == 1
 *
 *
 */

// @lc code=start
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> direction{-1, 0, 1, 0, -1};
    // 主函数
    int shortestBridge(vector<vector<int>> &grid) {
        int m = grid.size(), n = grid[0].size();
        queue<pair<int, int>> points;
        // dfs寻找第一个岛屿，并把1全部赋值为2
        bool flipped = false;
        for (int i = 0; i < m; ++i) {
            if (flipped)
                break;
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    dfs(points, grid, m, n, i, j);
                    flipped = true;
                    break;
                }
            }
        }
        // bfs寻找第二个岛屿，并把过程中经过的0赋值为2
        int x, y;
        int level = 0;
        while (!points.empty()) {
            ++level;
            int n_points = points.size();
            while (n_points--) {
                auto [r, c] = points.front();
                points.pop();
                for (int k = 0; k < 4; ++k) {
                    x = r + direction[k];
                    y = c + direction[k + 1];
                    if (x >= 0 && y >= 0 && x < m && y < n) {
                        if (grid[x][y] == 2) {
                            continue;
                        }
                        if (grid[x][y] == 1) {
                            return level;
                        }
                        points.push({x, y});
                        grid[x][y] = 2;
                    }
                }
            }
        }
        return 0;
    }

    // 辅函数
    void dfs(queue<pair<int, int>> &points, vector<vector<int>> &grid, int m, int n, int i, int j) {
        if (i < 0 || j < 0 || i == m || j == n || grid[i][j] == 2) {
            return;
        }
        if (grid[i][j] == 0) {
            points.push({i, j});
            return;
        }
        grid[i][j] = 2;
        dfs(points, grid, m, n, i - 1, j);
        dfs(points, grid, m, n, i + 1, j);
        dfs(points, grid, m, n, i, j - 1);
        dfs(points, grid, m, n, i, j + 1);
    }
};
// @lc code=end
